import java.util.Stack;

/*
 * @lc app=leetcode.cn id=84 lang=java
 *
 * [84] 柱状图中最大的矩形
 *
 * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/description/
 *
 * algorithms
 * Hard (37.32%)
 * Likes:    304
 * Dislikes: 0
 * Total Accepted:    16.8K
 * Total Submissions: 45K
 * Testcase Example:  '[2,1,5,6,2,3]'
 *
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 *
 *
 *
 *
 * 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
 *
 *
 *
 *
 *
 * 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
 *
 *
 *
 * 示例:
 *
 * 输入: [2,1,5,6,2,3]
 * 输出: 10
 *
 */

// @lc code=start
class Solution {

    public int largestRectangleArea(int[] heights) {
        Stack < Integer > stack = new Stack < > ();
        stack.push(-1);
        int maxarea = 0;
        for (int i = 0; i < heights.length; ++i) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])
                maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
            stack.push(i);
        }
        while (stack.peek() != -1)
            maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() -1));
        return maxarea;
    }

    /**

    public int largestRectangleArea(int[] heights) {
        if(heights.length == 0)
            return 0;
        return fun3(heights);
    }
    */

    //暴力
    int fun1(int[] heights) {
        int area = 0;
        for(int i=0; i < heights.length; i++) {
            int h = heights[i];
            for( int j = i; j < heights.length; j++) {
                h = Math.min(h, heights[j]);
                area = Math.max(area, h * (j-i+1));
            }
        }
        return area;
    }

    //分治
    int fun2(int[] heights, int left, int right) {
        if(left >= right)
            return heights[left];
        int mid = left;
        for(int index = left; index <= right; index++)  {
            if(heights[mid] > heights[index])
                mid = index;
        }
        //System.out.println(left+" "+mid+" "+right);
        int l = mid-1 >= left ? fun2(heights, left, mid-1) : 0;
        int r =  mid + 1 <= right ? fun2(heights, mid+1, right) : 0;
        int m = heights[mid] * (right - left + 1);
        return Math.max(m, Math.max(l, r));
    }

    //栈
    int fun3(int[] heights) {
        Stack<Integer> s = new Stack<>();
        int max = 0;
        s.add(-1);
        for(int i =0; i < heights.length; i++) {
            if(s.peek() == -1 || heights[s.peek()] < heights[i]) {
                s.add(i);
            } else {
                while(!(s.peek() == -1) && heights[s.peek()] > heights[i]) {
                    int index = s.pop();
                    max = Math.max(max, heights[index] *(i - s.peek() -1));
                }
                s.add(i);
            }
        }
        while(!(s.peek() == -1)) {
            int index = s.pop();
            max = Math.max(max, heights[index] *(heights.length-1 - s.peek()));
        }
        return max;
    }
}
// @lc code=end

